Methods of encrypting a plaintext message often employ substitutions of integers for plaintext message characters according to a substitution table. (See, for example, U.S. Pat. Nos. 5,307,412 and 5,335,280. In these patents, the substituted integers are called "numerical synonyms.") to thwart chosen plaintext attacks or frequency analysis of encrypted messages, it may be desirable to "update" or alter the substitution table periodically. The present invention provides a procedure for doing this.
The notion of altering substitution tables with the encryption of each plaintext character is not a new one. The mechanical or electro-mechanical Hagelin machines of an earlier era are examples of this. (See, for example, pp. 411-434 of Danid Kahn's "The Codebreakers," Macmillan, N.Y., 1967). They and other related devices and schemes are, however, quite different in spirit from the present invention.
First, the variable stepping rotors of such devices effectively alter the entire substitution table each time a plaintext character is encrypted. While this is acceptable for small alphabets (of 26 characters in the American military M-209 machine) and where high speed is not a requirement, it is impractical for large alphabets and the needs of high speed computerized encryption. In the present invention the numerical synonym, the integer substituted for a plaintext character, is not replaced with another until that character is used (unless it was previously involved in a transposition for a previously occurring plaintext character). Algebraically, instead of generating a permutation of the whole set of numerical synonyms-a whole new substitution table-the method of the present invention merely applies a two-cycle to the existing permutation (substitution table) at each stage of plaintext character encryption.
Second, systems of the existing type known in the art fail to make provision for a substitution table of size greater than .vertline.A.vertline..times..vertline.A.vertline., where .vertline.A.vertline. is the cardinality of the plaintext alphabet. An advantage of the present system is that it permits a substitution table of size the square of the cardinality of the set of addresses. This allows numerical synonyms for alphabet characters to be used and then to "disappear" for long stretches, thus degrading the statistics of repeated numerical synonym use.
Third, previous methods display the starting positions of the rotors (or their equivalents) in a fixed and ultimately determinable position in the ciphertext. In the present invention, the initializing seeds for the number generators, including the ones which determine the starting substitution table, are embedded in the initializing integer and can be recovered only by holders of the secret key.
A number generator (NG) may be either a pseudo-random number generator or it may be a secret, shared string of truly random digits. The "initializing seed" of the pseudo-random number generator then becomes the starting position index for the readout of a random digit string.
Terminology used in the sequel is drawn from that of U.S. Pat. No. 5,307,412.